A sequential pattern memory is a type of memory having many information storage locations where the information stored in one location, designated as a "child" location, is related to priorly stored information in another location. This other location is referred to as the "parent". In this parent-child relationship, each child has only one parent but each parent may have many children.
Adaptive sequential pattern memories are used in a variety of applications, such as data compression. The Lempel-Ziv-Welch (LZW) algorithm is a well-known data compression technique which is particularly desirable as it asymptotically reaches the provable maximum compression for large bodies of data. In an encoder, the operation of this algorithm may be summarized by stating that the encoder receives an input digital signal stream and "tokens" representative of digital signal sequences or "strings" formed from this stream are outputted. As this process continues, each transmitted token represents longer and longer strings, and thereby data compression is achieved. In the decoder, the transmitted tokens are decoded to recreate the digital signal stream. In any practical application, implementation of this algorithm involves the use of a memory for storing the tokens representative of the different strings.
Searching a memory refers to the operation of examining the contents of the memory to find stored information corresponding to the given input signal pattern. In data compression applications utilizing the LZW algorithm or others, the number of memory locations storing information grows rapidly. One problem with this growth is that the larger the memory to be searched, the longer the search time. Another problem with certain data compression algorithms, such as LZW, is that it is assumed that the memory is unbounded. Obviously, in practical applications, the memory size is finite and, once filled, some arrangements must be made to determine which information stored in memory should be discarded and replaced by new unstored information. This determination is complicated by the fact that the discarding of information in a parent location renders the information stored in any child of this parent invalid. Furthermore, the task of locating and discarding all children of any discarded parent can be a time-consuming process.
One prior art technique to update memories in data compression applications discards everything in memory once performance begins to slacken. As a result, data compression performance falters until the memory is rebuilt in both the encoder and decoder. Other techniques have discarded information based on a criteria which discards information deemed to be least valuable. These latter procedures have had to utilize far less than optimum criteria as information in parent locations could not be discarded without enduring the time-consuming process of locating and removing any child of a discarded parent.
It would, therefore, be desirable if a technique could be developed for finite sequential pattern memories which is fast, easily implementable and utilizes an efficient discarding criteria.